package leetcode.code0880;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	int[] starts;// 每一段开始
	int[] sizes;// 每一段长度
	int[] nums;// 每一段倍数
	long[] lens;// 每一段一倍长度
	long[] reachs;// 每一段nums倍长度
	char[] cs;

	public String decodeAtIndex(String s, int k) {
		char last = s.charAt(s.length() - 1);
		if (last < '2' || last > '9') {
			s += '1';
		}
		cs = s.toCharArray();
		int group = 0;
		for (char c : cs) {
			if (c >= '1' && c <= '9') {
				group++;
			}
		}
		starts = new int[group + 1];
		sizes = new int[group + 1];
		nums = new int[group + 1];
		lens = new long[group + 1];
		reachs = new long[group + 1];
		lens[0] = 1;
		int start = 0, id = 1;
		for (int i = 0; i < cs.length; i++) {
			char c = cs[i];
			if (c >= '1' && c <= '9') {
				starts[id] = start;
				nums[id] = c - '0';
				sizes[id] = i - start;
				lens[id] = reachs[id - 1] + sizes[id];
				reachs[id] = nums[id] * lens[id];
				id++;
				start = i + 1;
			}
		}
		// 在1~group组之间找第k个
		return this.find(1, group, k);
	}

	private String find(int L, int R, int k) {
		if (L == R && k < lens[L]) {// 可能需要mod一次
			int index = starts[L] + k - 1;
			return String.valueOf(cs[index]);
		}
		int l = L, r = R;
		int ans = 0;// 二分找到k属于哪一组
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			long reachm = reachs[mid];
			if (reachm >= k) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		int pos = (int) (k % lens[ans]);
		if (pos == 0) {// 余0 ，当前组最后一个字符
			while (sizes[ans] == 0) {// 跳过所有不含字符的组
				ans--;
			}
			int index = starts[ans] + sizes[ans] - 1;
			return String.valueOf(cs[index]);
		} else if (pos > reachs[ans - 1]) {// 大于前一组能达到的最大长度，说明答案在ans组里
			return this.find(ans, ans, (int) (pos - reachs[ans - 1]));
		} else {// 此刻说明答案同ans组没有关系
			return this.find(L, ans - 1, pos);
		}
	}

	@Override
	public void debug1() {
		HelpDebug.compare("a", this.decodeAtIndex("a23", 1));
		HelpDebug.compare("o", this.decodeAtIndex("leet2code3", 10));
//		"leetleetcodeleetleetcodeleetleetcode";
	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare("x", this.decodeAtIndex("leet2code3hello4max5nice", 835));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

		HelpDebug.compare("e", this.decodeAtIndex("leet2code3hello4max5nice", 18));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
